package demo4;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//top-k问题--设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可
class Tmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
public class Test {
    //方法1--直接排序
    public int[] smallestK1(int[] arr, int k) {
        Arrays.sort(arr);
        int [] topk = new int[k];
        for (int i = 0; i < k; i++) {
            topk[i] = arr[i];
        }
        return topk;
    }
    //方法2---使用小根堆:出K次----时间复杂度为O(N+k*log(n)),N为创建堆的复杂度,k*log(n)为出堆顶元素k次对应的复杂度
    public int[] smallestK2(int[] arr, int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] topk = new int[k];
        for (int i = 0; i < k; i++) {
            topk[i] = priorityQueue.poll();
        }
        return topk;
    }
    //方法3----使用容量为k的大根堆,先对数组的前k个数建立一个大根堆,然后从k+1开始,每个元素与大根堆堆顶元素进行对比,
    // 如果比堆顶元素小,则堆顶出堆,当前元素入堆---此时的时间复杂度为N*log(k),logk可以忽略,所以复杂度为N
    public int[] smallestK(int[] arr, int k){
        Tmp comparator = new Tmp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(comparator);
        int[] topk = new int[k];
        if (k == 0){//因为在PriorityQueue的初始大小是从1开始的,PriorityQueue的构造函数
            // PriorityQueue(int initialCapacity,Comparator<? super E> comparator)中可以
            // 看见initialCapacity的值小于1时会报错,但是题目k可以等于0,所以要`单独讨论
            return topk;
        }
        //创建容量为k的大根堆
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //将剩余数组元素与堆顶进行比较
        for (int i = k; i < arr.length; i++) {
            int top = priorityQueue.peek();
            //如果堆顶元素大于接下来的元素,就出堆顶元素,入当前数组元素
            if (top > arr[i]){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            topk[i] = priorityQueue.poll();
        }
        return topk;
    }

    public static void main(String[] args) {
        Test test = new Test();

    }
}
